/**
 * https://leetcode.cn/problems/open-the-lock/submissions/585580672/
 * 752. 打开转盘锁
 * medium 陈贝纯 2024.12.7
 * bfs
 */

class Solution {
public:
    char prev(char x){
        return (x=='0'?'9':x-1);
    }
    char next(char x){
        return (x=='9'?'0':x+1);
    }
    int openLock(vector<string>& deadends, string target) {
        if(target=="0000")
            return 0;
        unordered_set<string> st(deadends.begin(),deadends.end());
        if(st.count("0000"))
            return -1;
        queue<pair<string,int>> q;
        q.emplace("0000",0);
        unordered_set<string> rep={"0000"};
        while(!q.empty()){
            auto [ss,step]=q.front();
            q.pop();
            for(int i=0;i<4;++i){
                string sp=ss;
                sp[i]=prev(ss[i]);
                if(!rep.count(sp)&&!st.count(sp)){
                    if(sp==target)
                        return step+1;
                    q.emplace(sp,step+1);
                    rep.emplace(sp);
                }
                sp[i]=next(ss[i]);
                if(!rep.count(sp)&&!st.count(sp)){
                    if(sp==target)
                        return step+1;
                    q.emplace(sp,step+1);
                    rep.emplace(sp);
                }
            }
        }
        return -1;
    }
};

